
/**
 * @author mazouri
 * @create 2023-03-03 10:33
 */
public class _07_buildTree {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0) return null;
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int preL, int preR, int[] inorder, int inL, int inR) {
        if (preL > preR || inL > inR)
            return null;

        TreeNode root = new TreeNode(preorder[preL]);
        int rIndex = inL;
        for (; rIndex <= inR; rIndex++) {
            if (inorder[rIndex] == root.val) {
                break;
            }
        }

        root.left = build(preorder, preL + 1, preR + rIndex - inL, inorder, inL, rIndex - 1);
        root.right = build(preorder, preL + rIndex - inL + 1, preR, inorder, rIndex + 1, inR);
        return root;

    }
}
